Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có n mặt hàng có trọng lượng và giá trị khác nhau, nhưng hắn chỉ mang theo một cái túi có sức chứa về trọng lượng tối đa là M. Vậy kẻ trộm nên bỏ vào ba lô những món nào và số lượng bao nhiêu để đạt giá trị cao nhất trong khả năng mà hắn có thể mang đi được.

Dạng bài toán quyết định của bài toán xếp ba lô là câu hỏi "có thể đạt được một giá trị ít nhất là bao nhiêu theo phát biểu của bài toán".

Ta có n loại đồ vật, x1 tới xn. Mỗi đồ vật xj có một giá trị pj và một khối lượng wj. Khối lượng tối đa mà ta có thể mang trong ba lô là C.

Bài xếp ba lô dạng 0-1

Hạn chế số đồ vật thuộc mỗi loại là 0 (không được chọn) và 1 (được chọn).

Bài xếp ba lô 0-1 có thể được phát biểu bằng toán học như sau:Cực đại hóa ∑ j = 1 n p j x j . {\displaystyle \sum _{j=1}^{n}p_{j}x_{j}.} sao cho ∑ j = 1 n w j x j ≤ c , x j = 0 or 1 , j = 1 , … , n . {\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq c,\quad \quad x_{j}=0\;{\mbox{or}}\;1,\quad j=1,\dots ,n.}

Bài xếp ba lô bị chặn hạn chế số đồ vật không được vượt quá một lượng nào đó.

Bài xếp ba lô bị chặn có thể được phát biểu bằng toán học như sau:Cực đại hóa ∑ j = 1 n p j x j . {\displaystyle \sum _{j=1}^{n}p_{j}x_{j}.} sao cho ∑ j = 1 n w j x j ≤ c , 0 ≤ x j ≤ b j , j = 1 , … , n . {\displaystyle \sum _{j=1}^{n}w_{j}x_{j}\leq c,\quad \quad 0\leq x_{j}\leq b_{j},\quad j=1,\dots ,n.}

Bài xếp ba lô không bị chặn không có một hạn chế nào về số lượng đồ vật.

Trường hợp đặc biệt

Bài toán với các tính chất:

• là một bài toán quyết định
• là một bài toán 0/1
• với mỗi đồ vật, chi phí bằng giá trị: C = V

Lưu ý rằng trong trường hợp đặc biệt này, bài toán tương đương với:

Cho một tập các số nguyên, tồn tại hay không một tập con có tổng đúng bằng C?

Hoặc nếu đồ vật được phép có chi phí âm và C được chọn bằng 0, bài toán có dạng:

Cho trước một tập các số nguyên, tồn tại hay không một tập con có tổng đúng bằng 0?

Trường hợp đặc biệt này được gọi là bài toán tổng các tập con (subset sum problem). Với một số lý do, trong ngành mật mã học, người ta thường dùng cụm từ "bài toán xếp ba lô" khi thực ra đang có ý nói về "bài toán tổng con".

Bài toán xếp ba lô thường được giải bằng quy hoạch động, tuy chưa có một thuật toán thời gian đa thức cho bài toán tổng quát. Cả bài xếp ba lô tổng quát và bài toán tổng con đều là các bài NP-khó, và điều này dẫn đến các cố gắng sử dụng tổng con làm cơ sở cho các hệ thống mật mã hóa khóa công khai, chẳng hạn Merkle-Hellman. Các cố gắng này thường dùng nhóm thay vì các số nguyên. Merkle-Hellman và một số thuật toán tương tự khác đã bị phá, do các bài toán tổng con cụ thể mà họ tạo ra thực ra lại giải được bằng các thuật toán thời gian đa thức.

Phiên bản bài toán quyết định của bài xếp ba lô được mô tả ở trên là NP-đầy đủ và trong thực tế là một trong 21 bài toán NP-đầy đủ của Karp.

Bài xếp ba lô dạng phân số

Với mỗi loại, có thể chọn một phần của nó (ví dụ: 1Kg bơ có thể được cắt ra thành nhiều phần để bỏ vào ba lô)